package midsearch;

/**
 * 题目 ：求平方根
 * 题目详述 ：
 * 给定一个非负整数 x ，计算并返回 x 的平方根，即实现int sqrt(int x)函数。
 * 正数的平方根有两个，只输出其中的正数平方根。
 * 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
 */
public class MySqrt {
    /**
     * 核心思想 ：
     * 由于题目条件要求的是 非负整数x的正数平方根；
     * ===》 即，假设所要求的正数平方根m满足 ：
     *      m * m <= n && (m + 1) * (m + 1) > n
     * 即，通过上述的两个条件，来判断某个数m是否为另一个数n的正数平方根；
     *
     * 需要注意的是，其对于 所输入值x的取值范围 ：0 <= x <= 2的31次方 - 1
     */
    public int mySqrt(int x) {
        long begin = 0;
        long end = x;
        while(begin <= end){
            long middle = (begin + end) / 2;
            if(middle * middle <= x){
                // 即，同时满足 ： m * m <= n && (m + 1) * (m + 1) > n 条件的话，那么就找到了当前元素n的平方根middle；
                if((middle + 1) * (middle + 1) > x){
                    return (int)middle;
                }
                // 若是middle不是所要寻找的正数平方根，那么由于middle平方 <= x，即所要查找的平方根还在后半部分
                begin = middle + 1;
            }
            else {
                end = middle - 1;
            }
        }
        // 没啥实际作用
        return -1;
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（logn） ===》 由于二分查找的时间复杂度，就是为O（logn）
     */
}
